跳到主要内容

1345.跳跃游戏 IV

· 阅读需 6 分钟

1、题干​

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：

  • i + 1 需满足：i + 1 < arr.length
  • i - 1 需满足：i - 1 >= 0
  • j 需满足：arr[i] == arr[j] 且 i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

 

示例 1：

输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。

示例 2：

输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。

示例 3：

输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。

 

提示：

  • 1 <= arr.length <= 5 * 104
  • -108 <= arr[i] <= 108

DFS解法写自闭了，简单写下BFS和动态规划的思路和代码

2、解法1-BFS​

BFS解法需要注意各种边界条件以及剪枝优化，不然很可能超时、内存溢出。剪枝的方法有这些：

  • 跳过相邻且值相同的节点，只留头尾，中间部分没有意义
  • 跳过已访问过的节点
  • BFS的当前层级超过到达该节点的最小步数

3、代码​

var minJumps = function (arr) {
    const n = arr.length;

    // 记录数字对应的索引以及最小步数
    const map = new Map();
    for (let i = 0; i < n; i++) {
        if (arr[i] === arr[i + 1] && arr[i] === arr[i - 1]) continue;
        map.get(arr[i]) ? map.get(arr[i])[0].push(i) : map.set(arr[i], [[i], Infinity]);
    }

    const visited = new Set();
    let queue = [0], level = 0, res = Infinity;

    while (queue.length) {
        const set = new Set();
        if (level >= res) break;
        for (const i of queue) {
            if (visited.has(i)) continue;
            visited.add(i);

            if (i === n - 1) res = Math.min(res, level);
            if (i >= 1) set.add(i - 1);
            if (i <= n - 2) set.add(i + 1);

            const [idxs, min] = map.get(arr[i]);
            if (level + 1 > min) continue;

            map.get(arr[i])[1] = Math.min(min, level + 1);
            for (const x of idxs) {
                if (x !== i) set.add(x);
            }
        }
        queue = [...set];
        level++;
    }

    return res;
};

4、执行结果​

  • 执行用时: 180 ms
  • 内存消耗: 62.3 MB

5、解法2-动态规划​

实际上这道题不能用动态规划，因为违反了无后效性，其实带来的问题就是不能一次性规划出结果，这个问题没啥好办法，多规几次就出来了（两次动态规划结果一致则认为已经是最优解）。

6、代码​

var minJumps = function (arr) {
    const n = arr.length;

    // 记录数字对应的索引
    const map = new Map();
    for (let i = 0; i < n; i++) {
        map.get(arr[i]) ? map.get(arr[i])[0].push(i) : map.set(arr[i], [[i], Infinity]);
    }

    // DP处理
    const dp = new Array(n).fill(Infinity);
    dp[0] = 0;

    function updateSame(i) {
        const [idxs, min] = map.get(arr[i]);
        if (idxs.length < 2 || dp[i] >= min) return;
        map.get(arr[i])[1] = dp[i];
        for (let j = 0; j < idxs.length; j++) {
            dp[idxs[j]] = Math.min(dp[i] + 1, dp[idxs[j]]);
        }
    }

    function runDp() {
        for (let i = 0; i < n; i++) {
            if (i > 0) dp[i - 1] = Math.min(dp[i] + 1, dp[i - 1]), updateSame(i - 1);
            if (i < n - 1) dp[i + 1] = Math.min(dp[i] + 1, dp[i + 1]), updateSame(i + 1);

            updateSame(i);
        }
    }

    while (1) {
        runDp();
        const r1 = dp.toString();
        runDp();
        const r2 = dp.toString();
        if (r1 === r2) return dp[n - 1];
    }
};

7、执行结果​

  • 执行用时: 380 ms
  • 内存消耗: 65.1 MB

8、解法3-DFS​

各种处理和优化，最终还是没能AC，直接贴代码吧，如果有大神看到希望指点下🙏

var minJumps = function (arr) {
    const n = arr.length;

    // 记录数字对应的索引以及最小步数
    const map = new Map();
    for (let i = 0; i < n; i++) {
        if (arr[i] === arr[i + 1] && arr[i] === arr[i - 1]) continue;
        map.get(arr[i]) ? map.get(arr[i])[0].push(i) : map.set(arr[i], [
            [i], Infinity
        ]);
    }

    let res = Infinity;

    function dfs(i, path) {
        if (i === n - 1) return res = Math.min(res, path.size);
        if (i < 0 || i > n - 1 || path.has(i)) return;

        const [idxs, min] = map.get(arr[i]);
        if (path.size >= min || path.size + 1 >= res) return;

        path.add(i);

        for (let j = 0; idxs.length > 1 && j < idxs.length; j++) {
            if (i !== idxs[j]) dfs(idxs[j], path);
        }

        dfs(i - 1, path);
        dfs(i + 1, path);

        map.get(arr[i])[1] = Math.min(map.get(arr[i])[1], path.size);
        path.delete(i);
    }

    return dfs(0, new Set()), res;
};